المكدس (Stack) والرتل (Queue) وأنواع البيانات المجردة (ADT)

في عالم علوم الحاسوب، تُعد هياكل البيانات من الركائز الأساسية التي تبنى عليها الخوارزميات وأنظمة البرمجة المتطورة. تُستخدم هياكل البيانات لتنظيم وتخزين البيانات بطريقة تتيح الوصول إليها ومعالجتها بكفاءة. من بين هذه الهياكل، يبرز المكدس (Stack) والرتل (Queue) كنوعين مهمين من أنواع البيانات المجردة (Abstract Data Types – ADT)، وهما يعكسان نموذجين مختلفين في طريقة تخزين البيانات وإدارتها. في هذا المقال، سوف نستعرض بالتفصيل مفهوم أنواع البيانات المجردة، ثم نتناول شرحًا مطولًا للمكدس والرتل، مع توضيح خصائصهما، عملياتهما، تطبيقاتهما، وأهميتهما في البرمجة وهياكل البيانات.

أولاً: أنواع البيانات المجردة (ADT) – المفهوم والتعريف

أنواع البيانات المجردة (ADT) هي نموذج نظري يُستخدم لوصف كيفية تنظيم البيانات وسلوك العمليات التي تُجرى عليها، دون التطرق إلى تفاصيل تنفيذها الفعلية في الذاكرة أو البرامج. بعبارة أخرى، ADT تحدد ما يمكن فعله بالبيانات (العمليات)، وليس كيفية تنفيذ ذلك. يهدف هذا التجريد إلى الفصل بين كيفية استخدام البيانات وما يحدث تحت الكواليس، مما يسهل التصميم، التحليل، وإعادة الاستخدام.

تُعرف أنواع البيانات المجردة بأنها مجموعة من القيم الممكنة (الدومين) ومجموعة من العمليات التي يمكن تنفيذها على هذه القيم. مثلاً، عند الحديث عن قائمة (List) كنوع بيانات مجرد، فإننا نعرف أن العمليات قد تشمل الإضافة، الحذف، البحث، دون تحديد كيفية تمثيل القائمة داخليًا.

الخصائص الأساسية لأنواع البيانات المجردة

1. التجريد: إخفاء تفاصيل التنفيذ والتركيز على الوظائف التي تقدمها.

2. التغليف: حماية البيانات من التلاعب المباشر، والاعتماد على واجهات واضحة للعمليات.

3. إعادة الاستخدام: إمكانية تطبيق نفس النموذج على أكثر من تنفيذ مختلف.

4. المرونة في التنفيذ: يمكن تنفيذ ADT باستخدام هياكل بيانات مختلفة بحسب الحاجة.

ثانياً: المكدس (Stack)

تعريف المكدس

المكدس هو نوع من أنواع البيانات المجردة يمثل مجموعة من العناصر منظمة بطريقة تعتمد مبدأ “Last In, First Out” أو ما يُعرف بـ LIFO، أي أن العنصر الذي يُضاف أخيرًا هو أول من يُزال. يمكن تصور المكدس كمجموعة من الأطباق المكدسة فوق بعضها البعض، حيث لا يمكن الوصول إلا إلى الطبق الموجود في الأعلى فقط.

العمليات الأساسية في المكدس

• الدفع (Push): إضافة عنصر جديد إلى قمة المكدس.

• السحب (Pop): إزالة العنصر الموجود في قمة المكدس وإرجاعه.

• التطلع (Peek أو Top): مشاهدة العنصر في القمة دون إزالته.

• التحقق من الفراغ (IsEmpty): التأكد مما إذا كان المكدس فارغًا.

• التحقق من الامتلاء (IsFull): التأكد مما إذا كان المكدس ممتلئًا (في حالة المكدس محدود السعة).

تطبيقات المكدس

1. إدارة استدعاءات الدوال في البرمجة: حيث يتم حفظ سياق الدالة عند استدعائها ثم استعادته عند الانتهاء.

2. إلغاء العمليات (Undo) في البرامج، مثل محررات النصوص.

3. معالجة التعبيرات الرياضية: تحويل التعبيرات من الشكل الوسيط إلى الشكل اللاحق (Postfix) أو السابق (Prefix).

4. تتبع العمليات في الخوارزميات، مثل البحث في الشجرة أو الرسم البياني.

5. الملاحة داخل صفحات الويب: زر “رجوع” (Back) في المتصفحات يستخدم مكدسًا لتتبع الصفحات التي تم زيارتها.

الهيكل الداخلي للمكدس

يمكن تنفيذ المكدس باستخدام مصفوفة أو قائمة مرتبطة (Linked List):

• المصفوفة: تتميز بسرعة الوصول الثابت (O(1)) ولكنها محدودة بالسعة.

• القائمة المرتبطة: تسمح بالتوسع الديناميكي دون قيد على السعة، ولكن تكلفة الوصول قد تكون أكبر قليلًا.

ثالثاً: الرتل (Queue)

تعريف الرتل

الرتل هو نوع آخر من أنواع البيانات المجردة، يتم تنظيمه على مبدأ “First In, First Out” أو FIFO، أي أن العنصر الذي يدخل أولاً هو أول من يخرج. يمكن تشبيه الرتل بطابور من الأشخاص ينتظرون خدمة، حيث يخدم أول من وصل أولاً.

العمليات الأساسية في الرتل

• الإدخال (Enqueue): إضافة عنصر في نهاية الرتل.

• الإخراج (Dequeue): إزالة العنصر من بداية الرتل.

• التحقق من الفراغ (IsEmpty): معرفة إذا كان الرتل فارغًا.

• التطلع إلى الأمام (Front أو Peek): عرض العنصر الأول في الرتل دون إزالته.

أنواع الرتل

1. الرتل العادي (Simple Queue): يتم فيه الإدخال من نهاية واحدة والإخراج من بداية واحدة.

2. الرتل الدائري (Circular Queue): يحل مشكلة استنفاد السعة في الرتل العادي بإعادة استخدام الأماكن الفارغة التي تُحرر عند الإخراج.

3. الرتل ذو الأولوية (Priority Queue): حيث يتم ترتيب العناصر حسب أولوية معينة وليس بالضرورة الترتيب الزمني للإدخال.

4. الرتل المزدوج (Deque): يسمح بالإدخال والإخراج من الطرفين، أي بداية ونهاية الرتل.

تطبيقات الرتل

1. إدارة الطابور في أنظمة الحوسبة مثل جدولة العمليات في أنظمة التشغيل.

2. نقل البيانات في شبكات الاتصالات.

3. المعالجة في أنظمة الطباعة، حيث يتم ترتيب المهام حسب زمن وصولها.

4. التعامل مع تدفقات البيانات المتسلسلة مثل ملفات الفيديو والصوت.

5. الخوارزميات التي تعتمد على الترتيب الزمني، مثل البحث في الرسم البياني بطريقة العرض أولاً (BFS).

الهيكل الداخلي للرتل

عادةً ما يتم تنفيذ الرتل باستخدام:

• مصفوفة: مع ضبط الفهارس لإدارة الإدخال والإخراج بشكل دائري.

• قائمة مرتبطة: تسمح بالمرونة والديناميكية في التعامل مع حجم الرتل.

مقارنة بين المكدس والرتل

أهمية المكدس والرتل في علوم الحاسوب

تلعب هياكل البيانات المكدس والرتل دورًا محوريًا في بناء الخوارزميات وتصميم البرامج، لما لها من خصائص تضمن كفاءة وسرعة في معالجة البيانات. ففهمهما هو أساس لفهم العديد من التقنيات والمفاهيم مثل:

• إدارة الذاكرة: تعتمد أنظمة التشغيل على المكدسات لتنفيذ استدعاءات الدوال بشكل متسلسل.

• تصميم الخوارزميات: خاصة في مجالات البحث والاستكشاف مثل البحث في الشجرة والرسوم البيانية.

• تطوير البرمجيات: حيث تستخدم في عمليات التحكم في التدفق وإلغاء العمليات.

• الشبكات والاتصالات: حيث تُستخدم الرتل لتنظيم تدفق البيانات بطريقة مرتبة.

استنتاجات ونظرة مستقبلية

مع تطور مجال علوم الحاسوب وتنوع التطبيقات، يظل المكدس والرتل من أهم أنواع البيانات المجردة التي يجب أن يتمتع بها كل مبرمج ومهندس برمجيات. تتطور طرق تنفيذها، وتزداد تنوعًا بما يناسب احتياجات الأنظمة الحديثة، مثل استخدام الرتل الدائري والرتل ذي الأولوية.

في المستقبل، من المتوقع أن تستمر أهمية هذه الهياكل في ظل ازدياد تعقيد الأنظمة وتنامي حاجات المعالجة الفورية والمرتبة للبيانات، خصوصًا مع توسع الحوسبة الموزعة والذكاء الاصطناعي، حيث تبقى إدارة البيانات بشكل فعّال ومحكم من الأولويات التي لا يمكن الاستغناء عنها.

مصادر ومراجع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms,” MIT Press, 3rd Edition, 2009.

• Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++,” 4th Edition, Pearson, 2013.

هذا المقال يوفر تغطية واسعة وعميقة لهياكل البيانات المكدس والرتل ضمن إطار أنواع البيانات المجردة، ويبرز أهميتهما التطبيقية والنظرية في علوم الحاسوب.